The hash function is a well known mathematical function that is widely used in the field of cryptography for transforming input ‘messages’ into fixed length output message digests. Ideal hash functions are assumed to be intractable and collision free, namely the original text cannot be obtained from the message digest or hash value and any two different messages will produce different hash values. In other words, a collision-free hash function maps arbitrarily long inputs to outputs of a fixed length, but in such a way that it is computationally infeasible to find a collision (two distinct messages x, y which map to the same output). Various collision-free and collision resistant functions have been proposed, e.g. for hashing messages before digitally signing them with the expectation of only needing to sign the relatively shorter hash value.
One such collision-free hashing paradigm provides the Multiplicative Hash (MuHash) and Additive Hash (AdHash) designed by Bellare and Micciancio (Bellare, M. and Micciancio, D; “A New Paradigm for Collision-free Hashing: Incrementality at Reduced Cost; November 1996). The collision-free hash functions designed by Bellare and Micciancio intend to also enable incrementality, meaning if a message x which has been previously hashed is modified to produce x′, then rather than having to re-compute the hash of x′ from scratch, an “update” of the old hash can quickly be obtained. In this way, if blocks of the messages can be replaced, the new hash can be computed using knowledge of only the old and new blocks, and the old hash thus enabling the new hash to be computed much faster than the old hash.
The MuHash comprises dividing a message into blocks. Each block is concatenated with a unique index value. The block is then mapped into a multiplicative group using a pre-existing hash function. All of the group elements, each corresponding to a block of the message are then multiplied together, to yield a hash value. In order to prove the MuHash is collision resistant, Bellare and Micciancio assumed: a) the pre-existing hash to be a random oracle, namely where the hash is drawn at random from some family of functions, and then made public; and b) the discrete logarithm in the multiplicative group is intractable.
In addition to being incremental, the MuHash was shown to be parallelizable, which provides efficiencies, in particular when implementing the MuHash in hardware. As noted above, MuHash requires a pre-existing hash, in particular a fixed-input-length hash. The security proof for MuHash models this hash by a random oracle, which is considered a strong assumption. Furthermore, MuHash is only collision resistant if the pre-existing hash is collision resistant.